package chapter8;

/**
 * 线性时间排序-桶排序
 *
 * 非原址排序-最坏/平均O(n)
 */
public class BucketSort {

    public static double[] bucketSort(double[] A) {
        int n = A.length;
        Node[] B = new Node[n];
        // 赋值,冲突对链表追加
        for (int i = 0; i < n; i++) {
            // 均匀分布到各个槽位,由于是对A数组的元素进行hash,所以槽位越小则相对于在数组中的其他元素越小
            int index = (int) (n * A[i]);
            if (B[index] != null) {
                Node next = B[index];
                while (next != null) {
                    if (next.next == null) {
                        next.next = new Node(A[i]);
                        break;
                    }
                    next = next.next;
                }
            } else {
                B[index] = new Node(A[i]);
            }
        }
        // 用插入排序对每个槽位的链表进行排序,排序后按照hash的规则,越小的槽位的链表相对于其他槽位的链表值越小
        for (int i = 0; i < n; i++) {
            if (B[i] != null) {
                B[i] = insertionSort(B[i]);
            }
        }
        // 从小槽位开始遍历,赋值
        double[] C = new double[n];
        int counter = 0;
        for (int i = 0; i < n; i++) {
            if (B[i] != null) {
                Node next = B[i];
                while (next != null) {
                    C[counter] = next.value;
                    counter++;
                    next = next.next;
                }
            }
        }
        return C;
    }

    private static Node insertionSort(Node B) {
        int counter = 0;
        Node next = B;
        while (next != null) {
            counter++;
            next = next.next;
        }

        double[] C = new double[counter];
        next = B;
        for (int i = 0; i < counter; i++) {
            C[i] = next.value;
            next = next.next;
        }
        insertionSort(C);

        Node D = new Node(C[0]);
        Node D1 = D;
        for (int i = 1; i < counter; i++) {
            D1.next = new Node(C[i]);
            D1 = D1.next;
        }
        return D;
    }

    private static void insertionSort(double[] A) {
        for (int j = 1; j < A.length; j++) {
            double key = A[j];
            int i = j - 1;
            while (i >= 0 && A[i] > key) {
                A[i + 1] = A[i];
                i = i - 1;
            }
            A[i + 1] = key;
        }
    }

    static class Node {

        public double value;
        public Node next;

        public Node() {

        }

        public Node(double value) {
            this.value = value;
        }

    }

}
